/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-02-16
 * Time: 11:05
 */
public class Solution2 {
    /*  要使时间复杂度为O(n*logn),而空间复杂度是O（1），那么就要使用迭代版，也就是自底而上的排序
       对于非递归的排序链表则不太好理解，原理就是非递归版的归并排序数组，方法是：
       ①：求得链表长度，在循环中手动设置归并段的长度，在这段长度里面进行归并排序
         一开始以一个节点一个节点为一组，然后合并成两个节点的子链表，那么下一个节点是怎么确定的呢，对于数组
         第二个归并段的开头就是s2=s1(第一个归并段开头）+gap(步数）-1，确定好两个归并段的头才可以进行归并排序
         那么对于链表的分组也是一样的道理，每个组的节点个数（也就是两个归并段的长度，两个归并头节点的距离）
         这个归并段的长度在归并排序完之后以二倍的形式增长，直到长度大于等于原来链表的长度就排序完成了

       ②：  对于确定每一个归并段，肯定是要分割链表的，分割链表的方法就是根据事先知道的归并段的长度去分割成两段归并段
       ③：  然后就是合并链表，方法和之前的一样，那么合并完归并段之后，我们需要把排序完的链表的所有节点连接起来
            当每一组排完序之后就又要从头开始，开始下一组排序，下一组排序的归并段的长度是上一次的两倍

    * */
    public ListNode sortList(ListNode head) {
        int len=getLen(head);//先得到链表长度
        //需要构造一个新的虚拟头节点，因为要排序的话，头结点不一定是排好序的链表的头结点，用原来的头结点的话，顺序是不确定的
        ListNode dummyHead=new ListNode(0);
        //让虚拟头节点连接原来的头结点，这样在排完序之后直接返回虚拟节点的next域即可
        dummyHead.next=head;
        //分组排序链表
        for(int step = 1;step<len;step*=2){
            //每一次的归并段的查找以及合并都要重新从头结点出发
            ListNode prev=dummyHead;//用于连接排好序的每个归并段
            ListNode cur=dummyHead.next;//遍历链表实现分割归并段
            while(cur != null){
                //开始分割归并段
                ListNode h1=cur;//左边归并段的头
                ListNode h2=split(h1,step);//右边归并段的头
                //下一组左边归并段的头要先记录好
                cur=split(h2,step);
                //然后是合并归并段
                ListNode mergeHead=mergeList(h1,h2);
                //然后是把合并好的连接起来，供下一次分割归并段使用
                prev.next=mergeHead;
                while(prev.next !=null){
                    prev=prev.next;//走到每个排好序的归并段的末尾，说明一次的归并排序完成
                }
            }
        }
        return  dummyHead.next;
    }
    //实现分割归并段的函数
    public static  ListNode split(ListNode head,int step){
        if(head == null){
            return  head;
        }
        ListNode cur=head;//遍历链表
        //走step步,分割成两个链表
        for(int i = 1;i<step && cur.next!=null;i++){
                cur=cur.next;
        }
        //走完了，说明确定好了每组的节点个数，需要记录下一组归并段的起点
        ListNode next_head=cur.next;
        cur.next = null;
        return next_head;
    }
    //实现求链表长度的函数
    public int getLen(ListNode head){
        int len = 0;
        while(head!=null){
            len++;
            head=head.next;
        }
        return len;
    }
    //实现归并排序的函数
    public ListNode mergeList(ListNode h1,ListNode h2){
        //新的虚拟头节点
        ListNode newH=new ListNode(0);
        ListNode cur=newH;
        while(h1 != null && h2 != null){
            if(h1.val<h2.val){
                cur.next = h1;
                h1=h1.next;
            }else{
                cur.next = h2;
                h2 = h2.next;
            }
            cur=cur.next;
        }
        if(h1==null){
            cur.next = h2;
        }
        if(h2 == null){
            cur.next = h1;
        }
        return  newH.next;
    }

}
